package Demo3;

/**
 * @ClassName SeparateCircularLinkedList
 * @Description TODO
 * @Author ZJX
 * @Date 2024/9/17 21:26
 * @Version 1.0
 */
public class SeparateCircularLinkedList {
    static class Node {
        char data;
        Node next;

        public Node(char data) {
            this.data = data;
            this.next = null;
        }
    }

    // 插入节点到循环链表的尾部
    public static Node insertToCircularList(Node tail, Node newNode) {
        if (tail == null) {
            // 如果链表为空，新节点就是尾节点，同时也是头节点
            newNode.next = newNode; // 形成自环
            return newNode; // 返回新链表的尾节点
        } else {
            // 如果链表不为空，将新节点插入到尾节点之后
            newNode.next = tail.next; // 新节点指向头节点
            tail.next = newNode;      // 尾节点指向新节点
            return newNode;           // 更新尾节点为新节点
        }
    }

    // 根据字符分类插入到不同的循环链表中
    public static void separateList(Node head, Node h1, Node h2, Node h3) {
        Node cur = head; // 当前遍历的节点
        Node tail1 = null, tail2 = null, tail3 = null; // 三个链表的尾节点

        while (cur != null) {
            Node nextNode = cur.next; // 记录下一个节点
            cur.next = null; // 断开当前节点的 next 指针

            // 分类存储
            if (isDigit(cur.data)) {
                tail1 = insertToCircularList(tail1, cur); // 插入数字链表
                h1.next = (tail1 == null) ? null : tail1.next; // h1 头结点指向数字链表的头
            } else if (isLetter(cur.data)) {
                tail2 = insertToCircularList(tail2, cur); // 插入字母链表
                h2.next = (tail2 == null) ? null : tail2.next; // h2 头结点指向字母链表的头
            } else {
                tail3 = insertToCircularList(tail3, cur); // 插入其他字符链表
                h3.next = (tail3 == null) ? null : tail3.next; // h3 头结点指向其他字符链表的头
            }

            cur = nextNode; // 处理下一个节点
        }
    }

    // 打印循环链表
    public static void printCircularList(Node tail, String name) {
        if (tail == null) {
            System.out.println(name + " 链表为空");
            return;
        }

        Node cur = tail.next; // 从头节点开始打印
        System.out.print(name + ": ");
        do {
            System.out.print(cur.data + " ");
            cur = cur.next;
        } while (cur != tail.next); // 遍历直到回到头节点
        System.out.println();
    }

    // 创建一个简单的单链表
    public static Node createList(char[] data) {
        Node head = null, tail = null;
        for (char c : data) {
            Node newNode = new Node(c);
            if (head == null) {
                head = newNode;
                tail = newNode;
            } else {
                tail.next = newNode;
                tail = newNode;
            }
        }
        return head;
    }

    // 判断字符是否为数字
    private static boolean isDigit(char ch) {
        return '0' <= ch && ch <= '9';
    }

    // 判断字符是否为字母
    private static boolean isLetter(char ch) {
        return ('A' <= ch && ch <= 'Z') || ('a' <= ch && ch <= 'z');
    }

    public static void main(String[] args) {
        // 原始链表数据
        char[] data = {'1', 'c', '！', '2', 'h', '$', '3', 'i', 'n', '#', 'a'};
        Node originalList = createList(data);

        // 创建头结点（占位，实际链表头从 tail.next 开始）
        Node h1 = new Node('H'); // 存储数字
        Node h2 = new Node('H'); // 存储字母
        Node h3 = new Node('H'); // 存储其他字符

        // 将原链表拆分为三个循环链表
        separateList(originalList, h1, h2, h3);

        // 打印三个循环链表
        printCircularList(h1.next, "数字链表");
        printCircularList(h2.next, "字母链表");
        printCircularList(h3.next, "其他字符链表");
    }
}